package jalgebrava.group;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.apache.log4j.Logger;

public class Subgroup<G> extends Subset<G> {
	private static final Logger logger = Logger.getLogger(Subgroup.class);
	
	private Subgroup(Group<G> inGroup, Iterable<G> gs) {
		super(inGroup, gs);
	}
	
	public Subgroup(Subset<G> subset) {
		super(subset.getGroup(), subset);
	}

	public static <G> Subgroup<G> generate(ElementsIterable<G> gs) {
		return generate(gs.getGroup(), gs);
	}
	
	/** 
	 * TODO this one belongs somewhere else!
	 */
	public static <G> List<G> powers(Group<G> group, G g) {
		LinkedList<G> result = new LinkedList<G>();
		G e = group.unit();
		result.add(e);		
		G x = g;
		while (!group.equals(x,e)) {
			result.add(x);
			x = group.mul(x, g);
		}
		return result;
		
	}
	public static <G> Subgroup<G> generate(Group<G> group, G g) {
		return generate(group, group.element(g));
	}
	private static <G> Subgroup<G> generate(Group<G> group, Iterable<G> s) {
		Set<G> elements = new HashSet<G>();
		elements.add(group.unit());
		boolean elementsHaveGrown;
		do {
			Set<G> newElements = new HashSet<G>(elements);
			
			for (G g1 : elements) {
		
				for (G g2 : s) {
					G toAdd = group.mul(g1, g2); 
					newElements.add(toAdd);
				}
			}
			elementsHaveGrown = newElements.size() > elements.size();
			elements = newElements;
		} while (elementsHaveGrown);
		
		return new Subgroup<G>(group, elements);
	}
	public final boolean isNormal() {
		logger.debug("Verifying normality of " + this);
		for (G x: getGroup()) {
			Subset<G> xh = GroupUtil.mul(x, this);
			Subset<G> hx = GroupUtil.mul(this, x); 
			if (!xh.equals(hx)) {				
				logger.debug(xh + " != "+ hx + " [x="+x+",h="+this+"]");
				return false;
			}
		}
		return true;
	}
	
}
